''Hacker's Delight'' is a software algorithm book by Henry S. Warren, Jr. first published in 2002. It presents fast bit-level and low-level arithmetic

algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...

for common tasks such as counting bits or improving speed of division by using multiplication.

Background

The author, an IBM researcher working on systems ranging from the

IBM 704 The IBM 704 is a large digital mainframe computer introduced by IBM in 1954. It was the first mass-produced computer with hardware for floating-point arithmetic. The IBM 704 ''Manual of operation'' states: The type 704 Electronic Data-Pro ...

to the

PowerPC PowerPC (with the backronym Performance Optimization With Enhanced RISC – Performance Computing, sometimes abbreviated as PPC) is a reduced instruction set computer (RISC) instruction set architecture (ISA) created by the 1991 Apple Inc., App ...

, collected what he called "programming tricks" over the course of his career. These tricks concern efficient low-level manipulation of bit strings and numbers. According to the book's foreword by Guy L. Steele, the target audience includes

compiler In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...

writers and people writing high-performance code.

Summary

Programming examples are written in C and

assembler Assembler may refer to: Arts and media * Nobukazu Takemura, avant-garde electronic musician, stage name Assembler * Assemblers, a fictional race in the ''Star Wars'' universe * Assemblers, an alternative name of the superhero group Champions of ...

for a

RISC In computer engineering, a reduced instruction set computer (RISC) is a computer designed to simplify the individual instructions given to the computer to accomplish tasks. Compared to the instructions given to a complex instruction set comput ...

architecture similar, but not identical to

. Algorithms are given as formulas for any number of bits, the examples usually for 32 bits. Apart from the introduction, chapters are independent of each other, each focusing on a particular subject. Many algorithms in the book depend on

two's complement Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...

integer numbers. The subject matter of the second edition of the book includes algorithms for * Basic algorithms for manipulating individual bits, formulas for identities, inequalities, overflow detection for arithmetic operations and shifts * Rounding up and down to a multiple of a known power of 2, the next power of 2 and for detecting if an operation crossed a power-of-2 boundary * Checking bounds * Counting total,

leading In typography, leading ( ) is the space between adjacent lines of type; the exact definition varies. In hand typesetting, leading is the thin strips of lead (or aluminium) that were inserted between lines of type in the composing stick to incre ...

and trailing zeros * Searching for bit strings * Permutations of bits and bytes in a word * Software algorithms for multiplication * Integer division * Efficient integer division and calculating of the remainder when the divisor is known * Integer

square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...

and

cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the only r ...

roots * Unusual number systems, including base -2 * Transfer of values between floating point and

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

Cyclic redundancy check A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. Blocks of data entering these systems get a short ''check value'' attached, based on t ...

error-correcting code In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...

s and

Gray code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representati ...

s *

Hilbert curves The Hilbert curve (also known as the Hilbert space-filling curve) is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891, as a variant of the space-filling Peano curves discovered by Giusep ...

including a discussion of applications

Style

The style is that of an informal mathematical textbook. Formulas are used extensively. Mathematical proofs are given for some non-obvious algorithms, but are not the focus of the book.

Reception

Overall reception has been generally positive.

Publication history

The book was published by

Addison-Wesley Professional Addison-Wesley is an American publisher of textbooks and computer literature. It is an imprint of Pearson PLC, a global publishing and education company. In addition to publishing books, Addison-Wesley also distributes its technical titles through ...

. The first edition was released in 2002 and the second in 2013.

References

External links

Archive of Hacker's Delight website
2002 non-fiction books 2013 non-fiction books Computer programming books Addison-Wesley books Computer science books